package my.jwds.p216;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum3 {

    public static void main(String[] args) {
        CombinationSum3 obj = new CombinationSum3();
        System.out.println(obj.combinationSum3(2,18));
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        Integer[] nums = new Integer[k];
        Arrays.fill(nums,0);
        combinationSum3(k,n,nums ,res);
        return res;
    }

    public void combinationSum3(int k, int n,Integer [] nums,List<List<Integer>> res) {
        if (k == 0){
            if (n == 0)res.add(Arrays.asList(Arrays.copyOf(nums,nums.length)));
            return;
        }
        int forNum;
        if (nums.length == k){
            forNum = 1;
        }else {
            forNum = nums[nums.length - k -1]+1;
        }
        if (k == 1){
            if (n < 10 && n >= forNum){
                nums[nums.length - 1] = n;
                res.add(Arrays.asList(Arrays.copyOf(nums,nums.length)));
            }
            return;
        }

        for (; forNum <= 9 ; forNum++) {
            if ((forNum + forNum+k-1)/2.0 * k <= n){
                nums[nums.length - k] = forNum;
                combinationSum3(k-1,n - forNum,nums,res);
            }
        }
    }
}